package com.yuan.algorithms.动态规划;

/**
 * @author YouYuan
 * @contact 1265161633@qq.com
 * @date 2016年5月20日 上午9:02:20
 * @descript 一个正在抢劫商店的小偷发现了n个商品，第i个商品价值v[i]美元，重w[i]磅，v[i]和w[i]都是整数．
 * 这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳W磅重的商品，W是一个整数．他应该拿哪些商品呢？
 * （我们称这个问题是O-1背包问题，因为对每个商品，小偷要么把它完整拿走，要么把它留下；他不能只拿走一个商品的一部分，或者把一个商品拿走多次。）
 */
public class 背包问题 {

	public static void main(String[] args) {
		int[] v = {60, 100, 120};//商品价值
		int[] w = {10, 20, 30};//商品重量
		int W = 50;//背包最大承受重量
		boolean[] mark = new boolean[v.length];//用于标记是否选取对应的商品
		System.out.println(f(v, w, W, mark, 0, 0));
		for (int i = 0; i < mark.length; i++) {
			if (mark[i]) {
				System.out.print(v[i]+" ");
			}
		}
	}

	/**
	 * 计算背包能够装下的最大价值（待优化）
	 * @param v 商品价值
	 * @param w 商品重量
	 * @param space 剩余空间
	 * @param mark 标记数组
	 * @param current 当前位置
	 * @param cost 当前价值总值
	 */
	private static int f(int[] v, int[] w, int space, boolean[] mark, int current, int cost) {
		if (space <= 0 || current >= v.length) {
			return cost;
		}
		int cost_1 = 0;
		int cost_2 = 0;
		if (space - w[current] >= 0) {
			//选择当前商品
			cost_1 = f(v, w, space - w[current], mark, current+1, cost+v[current]);
		}
		//不选择当前商品
		cost_2 = f(v, w, space, mark, current+1, cost);
		if (cost_1 > cost_2) {
			mark[current] = true;
			return cost_1;
		} else {
			mark[current] = false;
			return cost_2;
		}
	}
}
